package exercise;

import test.list.LinkedList;
import test.list.Node;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Exercise004 {
    public static void main(String[] args) {
//        顺序表与ArrayList
//        //杨辉三角
//        int numRows = 8;
//        System.out.println(generate(numRows));



//        //链表与LinkedList①
//        //获取链表倒数第K个节点
//        LinkedList list = new LinkedList();
//        list.addLast(1);
//        list.addLast(2);
//        list.addLast(3);
//        Node ret = getLast(list.getHead(),1);
//        System.out.println(ret.value);
//        //给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
//        LinkedList list = new LinkedList();
//        list.addLast(4);
//        list.addLast(2);
//        list.addLast(3);
//        list.addLast(3);
//        list.addLast(2);
//        Node pHead = list.getHead();
//        int x = 3;
//        Node head = partition(pHead,x);
//        System.out.print("[");
//        for(Node cur = head;cur != null;cur = cur.next){
//            System.out.print(cur.value);
//            if(cur.next != null){
//                System.out.print(",");
//            }
//        }
//        System.out.print("]");
//        //判定链表是否是回文
//        LinkedList list = new LinkedList();
//        list.addLast(1);
//        list.addLast(2);
//        list.addLast(3);
//        list.addLast(2);
//        list.addLast(1);
//        Node A = list.getHead();
//        System.out.println(chkPalindrome(A));


//        //堆的基本概念
//        PriorityQueue<Integer> queue = new PriorityQueue<>();
//        queue.poll();

    }
    //链表与LinkedList①
    //单链表的逆置
    public Node reverseList(Node head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
//        Node h = new Node(head.value);
//        Node prev = h;
//        for(Node cur = head.next;cur != null;cur = cur.next){
//            h = new Node(cur.value);
//            h.next = prev;
//            if(cur.next != null)
//                prev = h;
//        }
//        return h;
        Node prev = null;
        Node cur = head;
        Node next = head.next;
        while(cur!= null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    //获取链表倒数第K个节点
    public static Node getLast(Node head,int k){
        if(head == null){
            return null;
        }
        int size = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            size++;
        }
        if(k > size){
            return null;
        }
        Node cur = head;
        for(int i = 0;i < size - k;i++){
            cur = cur.next;
        }
        return cur;
    }
    //合并两个有序链表
    //（做了好久，因为没有完全考虑到链表元素之间的连接性）
    public Node mergeTwoLists(Node list1, Node list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        Node newHead = null;
        Node newTail = null;
        Node cur1 = list1;
        Node cur2 = list2;
        Node next1 = cur1.next;
        Node next2 = cur2.next;
        while(cur1 != null && cur2 != null){
            next1 = cur1.next;
            next2 = cur2.next;
            if(cur1.value < cur2.value){
                if(newHead == null){
                    newHead = cur1;
                    newTail = cur1;
                }else{
                    newTail.next = cur1;
                    newTail = cur1;
                }
                cur1 = next1;
            }else{
                if(newHead == null){
                    newHead = cur2;
                    newTail = cur2;
                }else{
                    newTail.next = cur2;
                    newTail = cur2;
                }
                cur2 = next2;
            }
        }
        if(cur1 != null){
            newTail.next = cur1;
        }
        if(cur2 != null){
            newTail.next = cur2;
        }
        return newHead;
    }
    //给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    public static Node partition(Node pHead, int x) {
        //小于 x 的部分
        Node head1 = null;
        Node tail1 = null;
        //大于等于 x 的部分
        Node head2 = null;
        Node tail2 = null;
        for(Node cur = pHead;cur != null;cur = cur.next) {
            if (cur.value < x) {
                if (head1 == null) {
                    head1 = cur;
                    tail1 = cur;
                } else {
                    tail1.next = cur;
                    tail1 = cur;
                }
            } else {
                if (head2 == null) {
                    head2 = cur;
                    tail2 = cur;
                } else {
                    tail2.next = cur;
                    tail2 = cur;
                }
            }
        }
        if(head1 != null){
            tail1.next = null;
        }
        if(head2 != null){
            tail2.next = null;
        }
        if(tail1 == null){
            return head2;
        }
        tail1.next = head2;
        return head1;
    }
    //判定链表是否是回文
    public static boolean chkPalindrome(Node A) {
        if(A == null || A.next == null){
            return true;
        }
        int size = 0;
        for(Node cur = A;cur != null;cur = cur.next){
            size++;
        }
        Node B = A;
        int n = size/2;
        for(int i = 0;i < n ;i++){
            B = B.next;
        }
        Node cur = B;
        Node prev = null;
        Node next = null;
        if(B.next != null){
            while(cur != null){
                next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            B = prev;
        }
        Node cur1 = A;
        Node cur2 = B;
        for(int i = 0;i < n ;i++){
            if(cur1.value != cur2.value){
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }
    //

    //顺序表与ArrayList②
    //合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //容量
        int length = m + n;
        //特殊情况
        if(length == 0 || n == 0){
            return;
        }
        //b遍历nums2
        int b = 0;
        //a遍历nums1
        for(int a = 0;a < length;a++){
            //特殊情况结束
            if(m == length){
                return;
            }
            //如果比第a个小
            if(nums1[a] > nums2[b]){
                for(int i = m;i > a;i--){
                    nums1[i] = nums1[i - 1];
                }
                nums1[a] = nums2[b];
                m++;
                if(b < n - 1){
                    b++;
                }
            }
            //如果比最后一个大
            if(a == m - 1 && nums1[a] < nums2[b]){
                nums1[a + 1] = nums2[b];
                m++;
                if(b < n - 1){
                    b++;
                }
            }
            //如果nums1为空
            if(a == m){
                nums1[a] = nums2[b];
                m++;
                if(b < n - 1){
                    b++;
                }
            }
        }
    }



    //顺序表与ArrayList
    //原地移除数组中所有的元素val
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for(int i = 0;i < nums.length;i++)
        {
            if(nums[i] != val){
                nums[k] = nums[i];
                k++;
            }
        }
        k++;
        return k;
    }



    //顺序表与ArrayList
    //杨辉三角
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0;i < numRows;i++)
        {
            List<Integer> row = new ArrayList<>();
            for(int j = 0;j <= i;j++)
            {
                if(j == 0 || j == i)
                {
                    row.add(1);
                }else{
                    List<Integer> lastRow = ret.get(i - 1);
                    row.add(lastRow.get(j) + lastRow.get(j - 1));
                }
            }
            ret.add(row);
        }
        return ret;
    }

}
